776F - Sherlock's bet to Moriarty - CodeForces Solution

#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};
const ll oo = 1e18, MOD = 1e9 + 7;
const int N = 1e5 + 5, M = 1e6 + 5;
const ld PI = acos(-1.0), EPS = 1e-9;

int t, n, m, k, a[N], b[N], sz[N], vis[N];
int ans[N];
vector<int> v[N];
ll tot;

int find_sizes(int node, int p) {
    sz[node] = 1;
    for (auto x:v[node]) if (x != p && !vis[x]) sz[node] += find_sizes(x, node);
    return sz[node];
}

int get_centroid(int node, int p, int size) {
    for (auto x:v[node]) {
        if (x == p || vis[x]) continue;
        if (sz[x] > size) return get_centroid(x, node, size);
    }
    return node;
}

void init_centroid(int node, int level) {
    find_sizes(node, 0);
    int c = get_centroid(node, -1, sz[node] / 2);
    ans[c] = level;
    vis[c] = 1;
    for (auto x:v[c]) if (!vis[x]) init_centroid(x, level + 1);
}


//#define endl '\n'
int main() {
    //ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //freopen("marsllino.in", "r", stdin);
    //memset(dp, -1, sizeof dp);
    cin >> n >> k;
    set<int> s;
    for (int i = 1; i <= n; i++) s.insert(i);
    vector<pair<int, int>> tmp;
    for (int i = 1; i <= k; i++) {
        cin >> a[i] >> b[i];
        if (a[i] > b[i]) swap(a[i], b[i]);
        tmp.push_back({min(b[i] - a[i] - 1, n - (b[i] - a[i]) - 1), i});
    }
    sort(tmp.begin(), tmp.end());
    vector<vector<int>> v2;
    for (auto x:tmp) {
        vector<int> me = {a[x.second], b[x.second]};
        if (b[x.second] - a[x.second] - 1 < n - (b[x.second] - a[x.second]) - 1) {
            auto it = s.upper_bound(a[x.second]);
            while (it != s.end() && *it < b[x.second]) {
                me.push_back(*it);
                s.erase(it);
                it = s.upper_bound(a[x.second]);
            }
        } else {
            while (!s.empty() && *s.begin() < a[x.second]) {
                me.push_back(*s.begin());
                s.erase(s.begin());
            }
            while (!s.empty() && *s.rbegin() > b[x.second]) {
                me.push_back(*s.rbegin());
                s.erase(*s.rbegin());
            }
        }
        sort(me.rbegin(), me.rend());
        v2.push_back(me);
    }
    vector<int> remain;
    while (!s.empty()) {
        remain.push_back(*s.rbegin());
        s.erase(*s.rbegin());
    }
    v2.push_back(remain);
    sort(v2.begin(), v2.end());
    map<pair<int, int>, int> mp;
    int it = 0;
    for (auto x:v2) {
        it++;
        for (int i = 0; i < x.size(); i++) {
            int node1 = x[i], node2 = x[(i + 1) % x.size()];
            if (!mp[{node1, node2}]) mp[{node1, node2}] = mp[{node2, node1}] = it;
            else {
                v[mp[{node1, node2}]].push_back(it);
                v[it].push_back(mp[{node1, node2}]);
            }
        }
    }
    init_centroid(1, 1);
    for (int i = 1; i <= k + 1; i++) cout << ans[i] << " ";
    return 0;
}